package com.aug_leo.datastructure.deque;

import java.util.Iterator;

/**
 * 基于循环数组实现, 特点
 * <ul>
 *     <li>tail 停下来的位置不存储, 会浪费一个位置</li>
 * </ul>
 *
 * @param <E> 队列中元素类型
 */
public class ArrayDeque1<E> implements Deque<E>, Iterable<E> {

    /*
        h - head
        t - tail

        h
            t
        0   1   2   3
        a

        offerLast(a)    先添加元素 tail++
        offerLast(b)
        offerFirst(c)   先 head-- 再添加元素

        pollFirst()     先获取要移除的值 head++
        pollLast()      先 tail-- 再获取要移除的值

        head == tail 空
        head ~ tail == 数组长度-1 满
     */

    /**
     * 增加函数，用于在给定长度内对整数进行安全的递增操作
     * 如果当前值加1超出给定长度，则返回0，实现循环递增的效果
     *
     * @param i      当前的整数值
     * @param length 给定的长度限制
     * @return 递增后的值，超出长度时返回0
     */
    static int inc(int i, int length) {
        if (i + 1 >= length) {
            return 0;
        }
        return i + 1;
    }

    /**
     * 减少函数，用于在给定长度内对整数进行安全的递减操作
     * 如果当前值减1小于0，则返回给定长度减1的值，实现循环递减的效果
     *
     * @param i      当前的整数值
     * @param length 给定的长度限制
     * @return 递减后的值，小于0时返回给定长度减1的值
     */
    static int dec(int i, int length) {
        if (i - 1 < 0) {
            return length - 1;
        }
        return i - 1;
    }

    /**
     * 循环数组
     */
    E[] array;

    /**
     * 头指针
     */
    int head;

    /**
     * 尾指针
     */
    int tail;

    @SuppressWarnings("All")
    public ArrayDeque1(int capacity) {
        this.array = (E[]) new Object[capacity + 1];
    }

    /**
     * 在队列头部插入元素
     *
     * @param e 要插入的元素
     * @return 如果成功插入，则返回true， 否则返回 false
     */
    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        head = dec(this.head, array.length);
        array[head] = e;
        return true;
    }

    /**
     * 在队列尾部插入元素
     *
     * @param e 要插入的元素
     * @return 如果成功插入，则返回true, 否则返回 false
     */
    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        array[tail] = e;
        tail = inc(tail, array.length);
        return true;
    }

    /**
     * 移除并返回队列头部的元素
     *
     * @return 队列头部的元素，队列为空返回 null
     */
    @Override
    public E pollFirst() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        array[head] = null; // help GC
        head = inc(head, array.length);
        return value;
    }

    /**
     * 移除并返回队列尾部的元素
     *
     * @return 队列尾部的元素，队列为空返回 null
     */
    @Override
    public E pollLast() {
        if (isEmpty()) {
            return null;
        }
        tail = dec(tail, array.length);
        E value = array[tail];
        array[tail] = null; // help GC
        return value;
    }

    /**
     * 获取但不移除队列头部的元素
     *
     * @return 队列头部的元素，队列为空返回 null
     */
    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }

    /**
     * 获取但不移除队列尾部的元素
     *
     * @return 队列尾部的元素，队列为空返回 null
     */
    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        return array[dec(tail, array.length)];
    }

    /**
     * 判断队列是否为空
     *
     * @return 如果队列为空，则返回true，否则返回false
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    /*
        h
                    t
        0   1   2   3
        a   b   c
        tail > head
        3 - 0 == array.length - 1

     */

    /*
            h
        t
        0   1   2   3
            c   b   a
        tail < head
        head - tail == 1
     */

    /**
     * 判断队列是否已满
     * 注意：对于不支持容量限制的队列实现，此方法始终返回false
     *
     * @return 如果队列已满，则返回true，否则返回false
     */
    @Override
    public boolean isFull() {
        if (tail > head) {
            return tail - head == array.length - 1;
        } else if (tail < head) {
            return head - tail == 1;
        } else {
            return false;
        }
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            int pointer = head;

            @Override
            public boolean hasNext() {
                return pointer != tail;
            }

            @Override
            public E next() {
                E value = array[pointer];
                pointer = inc(pointer, array.length);
                return value;
            }
        };
    }
}
